package leetcode; /**
 * description:
 * author:zt
 * date:2021-10-12
 */

/**
 * 给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 *
 * 返回被除数dividend除以除数divisor得到的商。
 *
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 */
public class leetcode29 {
    int INF = Integer.MAX_VALUE;
    public int divide(int _a, int _b) {
        long a = _a, b = _b;
        boolean flag = false;  //标识正负
        if ((a<0&&b>0) || (a>0&&b<0)) flag = true;
        if (a<0) a = -a;
        if (b<0) b = -b;
        long l=0, r=a;
        while (l < r){
            long mid = l+r+1 >> 1;
            if (mul(mid,b) <= a) l = mid;
            else r = mid-1;
        }
        r = flag? -r:r;
        if (r > INF || r < -INF-1) return INF;
        return (int)r;
    }
    //不用乘除法，计算a*k的结果
    //从最低位开始累加a，如果k的最低位是1，表示1个a，
    // 此时k右移一位，a翻倍（因为k右移表示*2，如果右移的这一位是1，即表示2个a...
    long mul(long a,long k){
        long res = 0;
        while (k > 0){
            if ((k&1) == 1) res += a;
            k >>= 1;
            a *= 2;
        }
        return res;
    }
}
